# coding: utf8
# datetime: 2021-04-03
# describe: 个人测试， dfs求有效IP组合


from typing import List


def ip_combine(ip: str, index: int, res: List[int]) -> None:
    # 结束条件
    if index == len(ip)-1 or len(res) == 4:
        if index == len(ip)-1 and len(res) == 4:
            print(".".join(res))
        return
    
    # 寻找其他结果
    for i in range(4):
        sub_str = ip[index+1:index+1+i]
        if len(sub_str)>0:
            if (sub_str[0] != '0' and int(sub_str)<256) or sub_str == '0':
                res.append(sub_str)
                ip_combine(ip, index+i, res)
                res.pop()

ip_combine("19216801", -1, [])
